package com.formula.datastructure.exam.sort;

import com.formula.datastructure.util.DataUtil;

public class MergeSort {

    private Integer[] temp;

    public Integer[] sort(Integer[] array) {

        int N = array.length;
        temp = new Integer[N];

        mergesort(array, 0, N - 1);

        return array;
    }

    void mergesort(Integer[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergesort(array, low, mid);
            mergesort(array, mid + 1, high);
            merge(array, low, mid, high);
        }
    }

    void merge(Integer[] array, int low, int mid, int high) {
        int left = low;
        int right = mid + 1;
        int count = 0;

        while (left <= mid && right <= high) {
            if (array[left] <= array[right]) {
                temp[count++] = array[left++];
            } else {
                temp[count++] = array[right++];
            }
        }

        while (left <= mid) {
            temp[count++] = array[left++];
        }
        while (right <= high) {
            temp[count++] = array[right++];
        }

        count = 0;

        while (low <= high) {
            array[low++] = temp[count++];
        }
    }


    public static void main(String[] args) {
        MergeSort merge = new MergeSort();

        Integer[] array = DataUtil.genUniqueArray(12, 100);
        DataUtil.printIndex(12);
        DataUtil.printArray(array);
        DataUtil.printArray(merge.sort(array));
    }
}
